#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int INF=0x7fffffff;
const int maxn=1010;
int a[maxn],q[maxn];
long long dp[maxn][maxn],s[maxn],t[maxn];
int n,m;
long long min(long long x,long long y)
{
	return x<y?x:y;
}
bool check1(int i,int j1,int j2, long long K)
{
	int Y1=dp[i-1][j1]+(s[j1]*s[j1]+t[j1])/2;
	int Y2=dp[i-1][j2]+(s[j2]*s[j2]+t[j2])/2;
	if(Y2-Y1<K*(s[j2]-s[j1]))return true;
	return false;
}

bool check2(int i,int j1,int j2,int j3)
{
	int Y1=dp[i-1][j1]+(s[j1]*s[j1]+t[j1])/2;
	int Y2=dp[i-1][j2]+(s[j2]*s[j2]+t[j2])/2;
	int Y3=dp[i-1][j3]+(s[j3]*s[j3]+t[j3])/2;
	if((Y2-Y1)*(s[j3]-s[j2])>(Y3-Y2)*(s[j2]-s[j1]))return true;
	return false;
}

int main()
{
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)break;
		s[0]=t[0]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			s[i]=s[i-1]+a[i];
			t[i]=t[i-1]+a[i]*a[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			dp[0][i]=dp[0][i-1]+a[i]*s[i-1];
		int l,r;
		for(int i=1;i<=m;i++)
		{
			l=r=1;q[l]=i;
			for(int j=i+1;j<=n;j++)
			{
				while(l<r&&check1(i,q[l],q[l+1],s[j]))l++;
				int k=q[l];
				dp[i][j]=dp[i-1][k]+((s[j]-s[k])*(s[j]-s[k])-t[j]+t[k])/2;
				while(l<r&&check2(i,q[r-1],q[r],j))r--;
				r++;q[r]=j;
			}
		}
		printf("%lld\n",dp[m][n]);
	}
	return 0;
}


		


	
